Traveling Salesman

Traveling Salesman Problem

The traveling salesman problem is a classic problem of optimization that consists in finding the shortest path so that a salesman visits a set of cities. The correct answer is the cities itinerary so that the salesman visits each city only once returning to the city where he began the trip traveling a minimum distance.
El problema del vendedor viajero es un problema clásico de optimización que consiste en encontrar la ruta más corta para que un vendedor visite un grupo de ciudades. La respuesta correcta es el itinerario de ciudades de tal forma que el vendedor visite cada ciudad una sola vez regresando a la ciudad dónde comenzó el trayecto recorriendo una distancia mínima.

Problem 1
Using Microsoft Visual Studio create a Simulated Annealing Application using Wintempla. Set the name of the program to TravelingSalesman.
Usando Microsoft Visual Studio cree una Aplicación de Templado Simulado (Simulated Annealing Application) usando Wintempla. Fije el nombre del programa a TravelingSalesman.

Problem 2
Add the Paint event to the TravelingSalesman project:
  1. Open the TravelingSalesman.cpp file
  2. From the toolbar execute Wintempla
  3. Double click anywhere in the area of the window to open the properties dialog of the main window
  4. Open the Event tab
  5. Select the events as shown: App, Destroy, Paint and Timer
  6. Press OK to close the properties dialog
  7. Press OK to close Wintempla
Agregue el evento de Paint al proyecto TravelingSalesman:
  1. Abra el archivo TravelingSalesman.cpp
  2. Desde la barra de herramienta ejecute Wintempla
  3. Haga doble click en cualquier lugar de la ventana para abrir el diálogo de propiedades de la ventana principal
  4. Abra la pestaña de eventos
  5. Seleccione los eventos cómo se muestra: App, Destroy, Paint y Timer
  6. Presione OK para cerrar el diálogo de propiedades
  7. Presione OK para cerrar Wintempla

Event1

Event2

Event3

Traveling Salesman Perturbation

There are many ways to perturb the path in the traveling salesman problem. Usually, there are two typical methods: segment reversal and segment shift. Note that it is also possible to use both methods randomly.
Hay muchas formas para perturbar la ruta en el problema del vendedor viajero. Usualmente, hay dos métodos típicos: inversión de segmento y desplazamiento de segmento. Observe que es también posible usar ambos métodos en forma aleatoria.

Segment Reversal

Segment reversal is illustrated in the figure below. First, two random points are generated: A and B. These two points described the segment AB. Second, the order of the points in the segment is reversed.
La inversión de segmento es ilustrada en la figura de abajo. Primero, dos puntos aleatorios son generados: A y B. Estos dos puntos describen el segmento AB. Segundo, el orden de los puntos en el segmento se invierte.

SegmentReversal

Segment Shift

Segment shift is illustrated in the figure below. First, three random points are generated: A, B and C. Note that the points AB describe the segment AB. Second, the segment AB is removed from its original place, and it is inserted after the point C.
El desplazamiento de segmento es ilustrado en la figura de abajo. Primero, tres puntos aleatorios son generados: A, B y C. Observe que los puntos AB describen el segmento AB. Segundo, el segmento AB se remueve de su lugar original, y este es insertado después del punto C.

SegmentShift

Problem 4
Implement the Solution Coding for the traveling salesman problem.
Implemente la Codificación de la Solución para el problema del vendedor viajero.

Solution 4
The coding of this problem requires two variables as shown in the code below. The city variable is an array of POINTs to store the location of the 44 cities that will be used to run the simulation. The order variable is an array of integers values to indicate the order in which the cities will be traveled. For instance, if order[0] = 5, order[1] = 10, order[2] = 3, this would imply that the salesman should start his journey in city 5, going then to city 10, then going to city 3 and so on. Edit the Solution.h and Solution.cpp files as shown.
La codificación de este problema requiere dos variables como se muestra en el código de abajo. La variable city es un arreglo de puntos para almacenar la ubicación de las 44 ciudades que usarán para correr la simulación. La variable order es un arreglo de valores enteros para indicar el orden en el cual las ciudades serán recorridas. Por ejemplo, si order[0] = 5, order[1] = 10, order[2] = 3, esto implicaría que el vendedor debería comenzar su viaje en la ciudad 5, yendo después a la ciudad 10, entonces yendo a la ciudad 3, etc. Edite los archivos Solution.h y Solution.cpp.

Solution.h
#pragma once
#define NUM_CITIES 44

class Solution : public Math::ISimAnneal
{
public:
     Solution(void);
     ~Solution(void);
     //___________________________________________ Solution variables
     POINT city[NUM_CITIES];
     int order[NUM_CITIES];
     //___________________________________________ Math::ISimAnneal
     void SimAnnealInitialize();
     void SimAnnealPerturb(Math::ISimAnneal& original, double temperature, double initialTemperature);
     void SimAnnealCopy(const Math::ISimAnneal& source);
     double SimAnnealGetError();
private:
     double ComputeDistance(int city_index1, int city_index2);
     void SegmentReversal(Solution& original);
     void SegmentShift(Solution& original);
};

Solution.cpp
#include "StdAfx.h"
#include ".\Solution.h"

Solution::Solution(void)
{
     //_______________________________ Initialize to default values: city and order
     for(int i = 0; i < NUM_CITIES; i++)
     {
          city[i].x = 0;
          city[i].y = 0;
          order[i] = i;
     }
}

Solution::~Solution(void)
{
}

double Solution::ComputeDistance(int city_index1, int city_index2)
{
     return 0.0;
}

void Solution::SegmentReversal(Solution& original)
{
}

void Solution::SegmentShift(Solution& original)
{

}

void Solution::SimAnnealInitialize()
{
...


Problem 5
Edit the TravelingSalesman.h and TravelingSalesman.cpp files as shown to set the position of the 44 cities. The Window_Paint function provides the code to draw the cities and their positions. When the simulation ends, the order of the solution is displayed.
Edite los archivos TravelingSalesman.h y TravelingSalesman.cpp como se muestra para fijar la posición de las 44 ciudades. La función Window_Paint proporciona el código para dibujar las ciudades en sus posiciones. Cuando la simulación termina, el orden de la solución es mostrado.

CityLocation

TravelingSalesman.h
#pragma once //______________________________________ TravelingSalesman.h
#include "resource.h"
#include "Solution.h"
#define MAIN_TIMER 1
#define WORK_ID 1
class TravelingSalesman: public Win::Window
{
public:
     TravelingSalesman()
     {
     }
     ~TravelingSalesman()
     {
     }
     //__________________________ Used for display purposes
     POINT city[NUM_CITIES];
     int order[NUM_CITIES];
     //
     Mt::DoubleTs error;
...


TravelingSalesman.cpp
#include "stdafx.h" //________________________________________ TravelingSalesman.cpp
#include "TravelingSalesman.h"

int APIENTRY wWinMain(HINSTANCE hInstance, HINSTANCE , LPTSTR cmdLine, int cmdShow){
     TravelingSalesman app;
     app.CreateMainWindow(L"TravelingSalesman", cmdShow, IDI_TRAVELINGSALESMAN, NULL, (HBRUSH)(COLOR_WINDOW+1), hInstance);
     return app.MessageLoop(IDC_TRAVELINGSALESMAN);
}

void TravelingSalesman::Window_Open(Win::Event& e)
{
     //_____________________________________ Initialize the Random Generator
     Math::Statistics::random_generator.seed((unsigned int)::GetTickCount());
     int i;
     //___________________________________________ Set cities location
     city[0].x =704; city[0].y = 674; // City 0
     city[1].x =240; city[1].y = 532; // City 1
     city[2].x =641; city[2].y = 684; // City 2
     city[3].x =40; city[3].y = 428; // City 3
     city[4].x =117; city[4].y = 384; // City 4
     city[5].x =233; city[5].y = 97; // City 5
     city[6].x =704; city[6].y = 602; // City 6
     city[7].x =762; city[7].y = 336; // City 7
     city[8].x =431; city[8].y = 638; // City 8
     city[9].x =354; city[9].y = 631; // City 9
     city[10].x =578; city[10].y = 693; // City 10
     city[11].x =538; city[11].y = 573; // City 11
     city[12].x =716; city[12].y = 357; // City 12
     city[13].x =194; city[13].y = 589; // City 13
     city[14].x =141; city[14].y = 602; // City 14
     city[15].x =757; city[15].y = 157; // City 15
     city[16].x =194; city[16].y = 341; // City 16
     city[17].x =742; city[17].y = 208; // City 17
     city[18].x =313; city[18].y = 541; // City 18
     city[19].x =119; city[19].y = 162; // City 19
     city[20].x =728; city[20].y = 259; // City 20
     city[21].x =655; city[21].y = 119; // City 21
     city[22].x =672; city[22].y = 397; // City 22
     city[23].x =750; city[23].y = 471; // City 23
     city[24].x =286; city[24].y = 474; // City 24
     city[25].x =88; city[25].y = 614; // City 25
     city[26].x = 158; city[26].y = 121; // City 26
     city[27].x =305; city[27].y = 126; // City 27
     city[28].x =380; city[28].y = 94; // City 28
     city[29].x =491; city[29].y = 249; // City 29
     city[30].x =281; city[30].y = 220; // City 30
     city[31].x =206; city[31].y = 215; // City 31
     city[32].x =267; city[32].y = 331; // City 32
     city[33].x =332; city[33].y = 341;// City 33
     city[34].x =44; city[34].y = 498;// City 34
     city[35].x =688; city[35].y = 522; // City 35
     city[36].x =49; city[36].y = 568;// City 36
     city[37].x =559; city[37].y = 143;// City 37
     city[38].x =407; city[38].y = 336;// City 38
     city[39].x =482; city[39].y = 307;// City 39
     city[40].x =431; city[40].y = 230;// City 40
     city[41].x =470; city[41].y = 119;// City 41
     city[42].x =356; city[42].y = 225;// City 42
     city[43].x =131; city[43].y = 210;// City 43
     //
     //__________________________________________ Place the cities in sequence
     for(i = 0; i <NUM_CITIES; i++)
     {
          order[i] = i;
     }
     //__________________________________________ Copy the cities position to each solution
     for (i = 0; i <NUM_CITIES; i++)
     {
          solution.city[i] = city[i];
          solutionWork1.city[i] = city[i];
          solutionWork2.city[i] = city[i];
     }
     //__________________________________________ Simulated Annealing Setup
     simAnneal.goal = ...;
     simAnneal.initialTemp = ...;
     simAnneal.finalTemp = ...;
     simAnneal.numTemps = ...;
     simAnneal.numIterations = ...;
     simAnneal.cycles = ...;
     simAnneal.isCoolingScheduleLinear = ...;
     simAnneal.Setup(error, solution, solutionWork1, solutionWork2);
     simAnneal.SetPostMessage(hWnd, WM_APP, 0, WORK_ID);
     threadObject.BeginThread(simAnneal);
     this->timer.Set(MAIN_TIMER, 1000); //Every second
}

void TravelingSalesman::Window_Destroy(Win::Event& e)
{
     this->timer.Kill(MAIN_TIMER);
     ::PostQuitMessage(0);
     e.returnValue = 0;
}

void TravelingSalesman::Window_Timer(Win::Event& e)
{
     if (e.wParam == MAIN_TIMER)
     {
          wchar_t info[128];
          const double derror = error.Get();
          _snwprintf_s(info, 128, _TRUNCATE, L"error=%g, progress=%g", derror, threadObject.Progress);
          this->SetWindowText(info);
     }
}

void TravelingSalesman::Window_App(Win::Event& e)
{
     if (e.lParam == WORK_ID)
     {
          this->timer.Kill(MAIN_TIMER);
          threadObject.WaitForExit();
          this->Text = L"Done!";
          //___________________________ copy the optimized order to the city so that it can be displayed
          for (int i = 0; i <NUM_CITIES; i++)
          {
               order[i] = solution.order[i];
          }
          this->Repaint(NULL, true); // show the solution;
     }
}

void TravelingSalesman::Window_Paint(Win::Event& e)
{
     CG::Gdi gdi(hWnd, true, false);

     //_______________________________________ Create and select a blue brush
     CG::Brush brushBlue(RGB(0, 0, 255));
     gdi.Select(brushBlue);

     //_______________________________________ Draw the cities
     int i;
     wchar_t text[32];
     gdi.SetTextColor(RGB(150, 150, 190));
     int index;
     for(i = 0; i < NUM_CITIES; i++)
     {
          index = order[i];
          gdi.Circle(city[index].x, city[index].y, 3);
          _snwprintf_s(text, 32, _TRUNCATE, L"%d", i);
          gdi.TextOut(city[index].x+4, city[index].y+4, text);
     }

     //_______________________________________ Draw the trajectory
     int currentCity;
     int nextCity;

     for(i = 0; i < NUM_CITIES-1; i++)
     {
          currentCity = order[i];
          nextCity = order[i+1];
          gdi.Line(city[currentCity].x, city[currentCity].y, city[nextCity].x, city[nextCity].y);
     }

     //______________________________________ Draw a line between the last city and the first one
     currentCity = order[NUM_CITIES-1];
     nextCity = order[0];
     gdi.Line(city[currentCity].x, city[currentCity].y, city[nextCity].x, city[nextCity].y);
}


Problem 6
Implement the Initialization for the traveling salesman problem by writing the code of the SimAnnealInitialize() function in the Solution.cpp file. You may initialize the solution in any way as long as the solution be valid; for instance, the salesman cannot visit a city twice.
Implemente la Inicialización para el problema del vendedor viajero escribiendo el código de la función SimAnnealInitialize() en el archivo Solución.cpp. Usted puede inicializar la solución de cualquier forma siempre y cuando la solución sea válida; por ejemplo, el vendedor no puede visitar una ciudad dos veces.

Problem 7
Implement the Error Evaluation for the traveling salesman problem by writing the code of the SimAnnealGetError () function in the Solution.cpp file. Remember that the salesman must travel the shortest distance passing by all cities only once.
Implemente la Evaluación del Error para el problema del vendedor viajero escribiendo el código de la función SimAnnealGetError() en el archivo Solución.cpp. Recuerde que el vendedor debe viajar la distancia más corta pasando por todas las ciudades sólo una vez.

Problem 8
Implement the Perturbation for the traveling salesman problem by writing the code of the SimAnnealPerturb() function in the Solution.cpp file. You may perturb the solution in any way you wish. However, in this case we will use Segment Reversal and Segment Shift. Thus, you must provide the code of the SegmentReversal and SegmentShift functions.
Implemente la Perturbación para el problema del vendedor viajero escribiendo el código de la función SimAnnealPerturb() en el archivo Solución.cpp. Usted puede perturbar la solución del cualquier forma que usted desee. Sin embargo, en este caso nosotros usaremos Inversión de Segmentos y Desplazamiento de segmentos. Así, usted debe proporcionar el código de las funciones: SegmentReversal y SegmentShift.

Solution.cpp
void Solution::SimAnnealPerturb(Math::ISimAnneal& original, double temperature, double initialTemperature)
{
     std::uniform_real<double> ur(-1.0, 1.0);
     if (ur(Math::Statistics::random_generator) > 0.0)
     {
          SegmentReversal((Solution&)original);
     }
     else
     {
          SegmentShift((Solution&)original);
     }
}


Problem 9
Set the simulated annealing parameters (number of temperature, initial temperature, ...) and run the simulation, you must get the solution shown below.
Fije los parámetros del templado simulado (los números de temperaturas, la temperatura inicial, ...) y corre la simulación, usted debe obtener la solución mostrada debajo.

Solution

© Copyright 2000-2021 Wintempla selo. All Rights Reserved. Jul 22 2021. Home